'''
https://leetcode.cn/problems/merge-two-sorted-lists/
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
'''

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def mergeTwoLists(self,list1:ListNode, list2:ListNode):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        newList = ListNode(-1)
        temp = newList
        p = list1
        q = list2
        while p and q:
            if p.val > q.val:
                temp.next = q
                q = q.next
            else:
                temp.next = p
                p = p.next
            temp = temp.next
        if p:
            temp.next = p
        if q:
            temp.next = q
    
        return newList.next 